A conventional signal processing process may include four parts, namely, sampling, compression, storage/transmission, and decompression. In the sampling process, data collection is first performed for an original signal according to the Nyquist sampling theorem, and then the collected data is compressed. In the compression process, the collected data is transformed first, and then a few coefficients with large absolute values are compressed and encoded, and other coefficients equal or close to zero are discarded. In the compression process, a majority of data obtained through the sampling is discarded.
In recent years, a new signal collection technology has been put forward, that is, a compressed sensing technology. The compressed sensing technology takes advantage of a feature that an original signal S is sparse. That is to say, the original signal has only K_sparse non-zero items with unknown positions after experiencing orthogonal transformation. The amount of data measured by using the compressed sensing technology is much smaller than the amount of data required in conventional sampling.
In the process of implementing compressed sensing, a measured value (non-adaptive linear projection) of the original signal S is obtained first, where the measured value is represented by equation (1.1):y=Φs  (1.1)
In the above equation, y is the measured value, Φ is a measurement matrix, and S is the original signal. The original signal S is represented as a column vector with N items, and has a sparse expression. That is to say, Ψs=x obtained after orthogonal transformation Ψ has only K_sparse (K_sparse<<N) non-zero items with unknown positions. The measured value y is a column vector with M items (M<<N & M>2K_sparse), and the measurement matrix Φ has M rows and N columns.
After the measured value y of the original signal is obtained and then stored/transmitted, signal reconstruction may be performed. In the prior art, a signal reconstruction method is: first, under a constraint condition y=Tx, X is found; and then according to equation s=ΨHx, S is calculated, where a matrix T=ΦΨH is called a sensing matrix, Φ is a measurement matrix, and Ψ is the orthogonal transformation. The sensing matrix T is also called a dictionary, and each column in the dictionary is also referred to as an atom.
The signal can be reconstructed by using an orthogonal matching pursuit method, which is implemented through the following steps.
Step 1: First, initialize variables for iteration, which is detailed as follows.
Step 1.1: Set an initial value {tilde over (y)} of a residual error to make {tilde over (y)}=y.
Step 1.2: Set an initial value of a base matrix B to be an empty matrix: B0=. The base matrix B selects column K that best matches a received signal y from a dictionary T to build a sparse approximation of y, and an index of a column already selected by the base matrix B is denoted as a column vector τ, and its initial value τ0 is an empty vector.
Step 1.3: Before the kth iteration in an iteration process starts, denote a column that is not selected into the base matrix B in a sensing matrix as TN+1−k=−(k−1), where −(k−1)=N−k+1, TN+1−k=−(k−1) has N+1−k columns, and an initial value is TN=T.
An initial value of an estimated value of sparse expression x is set to {circumflex over (x)}=0N, where 0N represents a zero column vector with N items, that is, a column vector with each item being zero.
The modulus of each column in the sensing matrix T is denoted as a column vector −(0)=[∥t(1)∥2 ∥t(2)∥2 . . . ∥t(N)∥2]T, where t(i) (i=1, 2, . . . , N) represents the ith column of T, ∥t(i)∥2 represents the modulus of a vector t(i), and [•]T represents transposition of the vector or a matrix [•].
A column vector −(0)=πN=[1 2 . . . N]T records sequence numbers of atoms that are not selected into the base matrix B.
Step 2: The initial value of k is 1. Then the following iteration starts.
Step 2.1: Calculate, by using formula (1.2), a correlation between the kth residual error and each column in the sensing matrix from which k−1 columns are deleted:−(k−1)=−(k−1){tilde over (y)}  (1.2)
In the above formula, −(k−1)=N−k+1, −(k−1) represents a matrix with M rows and −(k−1) columns, and when k=1, the residual error {tilde over (y)}=y, that is, the residual error {tilde over (y)} is equal to a measured value vector; and when k=1, −(k−1)=−(0)=TN=T, that is, −(k−1) is the sensing matrix T; and −(k−1) is a column vector with −(k−1) items, and its ith item represents the value of correlation between the ith column of −(k−1) and the residual error {tilde over (y)}. It should be noted that, −(k−1) includes −(k−1) columns, which are −(k−1) columns to be selected in the sensing matrix T, that is, −(k−1) atoms to be selected in the sensing matrix T; and −(k−1) is obtained by deleting k−1 columns from the sensing matrix T, where the k−1 columns have been selected and placed into the base matrix.
Step 2.2: Determine, by using formula (1.3), a sequence number of a column with the maximum correlation value:
                              ρ          k                =                              argmax                          i              =              1                                                      •                -                            ⁡                              (                                  k                  -                  1                                )                                              ⁢                                                                  q                i                                                    /                          δ              i                                                          (        1.3        )            
In the above formula, qi represents the ith item of −(k−1), δi represents the ith item of −(k−1), −(k−1) is a modulus of each column of −(k−1), and |•| represents the absolute value of a scalar ●.
Step 2.3: Update the column −(k−1) to be selected by the selected base matrix B and the sensing matrix.
A kth column is added to the base matrix B to make Bk=[Bk−1 t(ρk)], where t(ρk) represents the ρkth column of −(k−1). Correspondingly, the ρkth column, t(ρk), is deleted from −(k−1) to obtain −(k) for subsequent iteration. The initial value Bk−1=B1−1=B0 of the base matrix B is an empty matrix.
Step 2.4: According to τk−1, obtain an index τk of each column of the base matrix Bk; and according to an index −(k−1) of each column of −(k−1) and the modulus −(k−1) of each column, obtain an index −(k) of each column of −(k) and the modulus −(k) of each column.
τk=[τk−1T πρk]T is obtained, where πρk is the ρkth item in −(k−1); the ρkth item, πρk, is deleted from −(k−1) to obtain −(k) for subsequent iteration; and the ρkth item is deleted from −(k−1) to obtain −(k) for subsequent iteration.
Step 2.5: Update a weight coefficient of each column selected in the base matrix B and a corresponding residual error.
First, a column vector zk composed of the weight coefficients of the columns selected in the base matrix B is calculated by using formula (1.4):zk=(BkHBk)−1BkHy  (1.4)
In the above formula, (•)−1 represents an inverse matrix of the matrix (•). Then, the residual error {tilde over (y)} is obtained by using formula (1.5):{tilde over (y)}=y−Bkzk  (1.5)
If k<K (generally, K is smaller than or equal to K_sparse), the value of k increases by 1, and the process goes back to step 1.
Step 3: Recover the signal.
The initial value of the estimated value of sparse expression x is {circumflex over (x)}=0N. In {circumflex over (x)}, let the ρkth item be {circumflex over (x)}τk=zk (k=1, 2, . . . , K), where zk is the kth item of zK, and τk is the kth item of the vector τk. Then the original signal is calculated as ŝ=ΨH{circumflex over (x)}.
As can be seen from the above, when determining each column of the base matrix, it is necessary to determine the correlation between −(k−1) and each column of the residual error by using formula −(k−1)=−(k−1){tilde over (y)}. −(k−1) is a vector with −(k−1) rows and N columns, where the value of N is very large; therefore, the complexity of calculating −(k−1){tilde over (y)} is extremely high.
Therefore, an appropriate method is desired to ensure proper recovery of a signal and reduce the amount of calculation for reconstructing the signal.